package algorithmic_data_structure.前缀树;

import org.junit.Test;

/**
 * 本质就是一颗多叉树，每个节点中能表示的内容为途径这个节点的次数，以这个节点为结尾的次数，以及这个节点的子节点们
 *
 */
public class 前缀树 {
    class Node{
        int pass;//途经这个节点的字符串个数
        int end ;//以这个节点为结尾的字符串个数
        Node[] next;
        public Node(){
            pass = 0;
            end = 0;
            next = new Node[26];//这里默认节点都是 a~z
        }
    }
    class Tire{
        public Node root;
        public Tire(){
            root = new Node();
        }
        public void insert(String str){
            if (str == null){
                return ;
            }
            char[] word = str.toCharArray();
            Node node = root;
            node.pass++;//每个字符串都会途径头节点
            int path = 0;
            for (int i = 0; i < word.length; i++) {
                path = word[i] - 'a';
                if (node.next[path] == null){
                    node.next[path] = new Node();
                }
                node.next[path].pass++;
                node = node.next[path];
            }
            node.end++;//结束循环时node指向的是该个字符串末尾的那个字符
        }
        //删除前缀树中的某个字符串
        public boolean delete(String str){
            if (str == null){
                return false;
            }
            char[] word = str.toCharArray();
            int path = 0;
            Node node = root;
            for (int i = 0; i < word.length; i++) {
                path = word[i] - 'a';
                if (node.next[path] == null) {//先看一遍是否有这个字符串，避免删着删着，发现这个字符串/前缀并不存在于前缀树中
                    return false;
                }
                node = node.next[path];
            }
            node = root;
            node.pass--;
            for (int i = 0; i < word.length; i++) {
                path = word[i] - 'a';
                node.next[path].pass--;
                if (node.next[path].pass == 0){
                    node.next[path] = null;//整颗砍掉,都已经没有经过这个节点的可能了
                    return true;
                }
                node = node.next[path];
            }
            node.end--;
            //这里是不对的，没有以这个节点为结尾也不能删除啊，有可能途经呢，而且在上面的过程以及有了删除空分支的操作了
//            if (node.end == 0){
//                pre.next[path] = null;
//            }
            return true;
        }
        //找出字符串str在前缀树出现的次数
        public int search(String str){
            if (str == null){
                return 0;
            }
            char[] word = str.toCharArray();
            int path = 0;
            Node node = root;
            //找到最后一个字符串最后一个字符对应的节点即可
            for (int i = 0; i < word.length; i++) {
                path = word[i] - 'a';
                if (node.next[path] == null){
                    return -1;
                }
                node = node.next[path];
            }
            return node.end;
        }
        //找出以字符串str为前缀的字符串在前缀树出现的次数
        public int prefixNumber(String str){
            if (str == null){
                return 0;
            }
            char[] word = str.toCharArray();
            int path = 0;
            Node node = root;
            //找到最后一个字符串最后一个字符对应的节点即可
            for (int i = 0; i < word.length; i++) {
                path = word[i] - 'a';
                if (node.next[path] == null){
                    return -1;
                }
                node = node.next[path];
            }
            return node.pass;
        }
    }
    @Test
    public void test(){
        Tire tire = new Tire();
        tire.insert("ab");
        tire.insert("abc");
        tire.insert("abq");
        tire.insert("abcd");
        tire.insert("abce");
        tire.insert("abqa");
        tire.insert("abqb");
        System.out.println(tire.search("ab"));
        System.out.println(tire.prefixNumber("ab"));
        System.out.println(tire.prefixNumber("abc"));
        System.out.println(tire.delete("abc"));
        System.out.println(tire.delete("abcd"));
        System.out.println(tire.delete("abce"));
        System.out.println(tire.prefixNumber("abc"));//这里应该返回-1啊！！！
        System.out.println(tire.prefixNumber("abcd"));
        System.out.println(tire.prefixNumber("ab"));
        tire.insert("abcd");
        System.out.println(tire.prefixNumber("abcd"));
        System.out.println(tire.prefixNumber("abc"));
        System.out.println(tire.prefixNumber("ab"));
    }

}
